|
In cryptography, most public key cryptosystems are founded on problems that are believed to be intractable. The higher residuosity problem (also called the n th-residuosity problem) is one such problem. This problem is ''easier'' to solve than integer factorization, so the assumption that this problem is hard to solve is ''stronger'' than the assumption that integer factorization is hard. ==Mathematical Background== If ''n'' is an integer, then the integers modulo ''n'' form a ring. If ''n''=''pq'' where ''p'' and ''q'' are primes, then the Chinese remainder theorem tells us that : The group of units of any ring form a group, and the group of units in is traditionally denoted . From the isomorphism above, we have : as an isomorphism of ''groups''. Since ''p'' and ''q'' were assumed to be prime, the groups and are cyclic of orders ''p''-1 and ''q''-1 respectively. If ''d'' is a divisor of ''p''-1, then the set of ''d''th powers in form a subgroup of index ''d''. If gcd(''d'',''q''-1) = 1, then ''every'' element in is a ''d''th power, so the set of ''d''th powers in is also a subgroup of index ''d''. In general, if gcd(''d'',''q''-1) = ''g'', then there are (''q''-1)/(''g'') ''d''th powers in , so the set of ''d''th powers in has index ''dg''. This is most commonly seen when ''d''=2, and we are considering the subgroup of quadratic residues, it is well known that exactly one quarter of the elements in are quadratic residues (when ''n'' is the product of exactly two primes, as it is here). The important point is that for any divisor ''d'' of ''p''-1 (or ''q''-1) the set of ''d''th powers forms a subgroup of 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「higher residuosity problem」の詳細全文を読む スポンサード リンク
|